package com.mj.listen2._02_并查集;

import com.mj.listen2._02_并查集.generic.GenericUnionFind;

public class Main {

    static final int count = 2000000;

    public static void main(String[] args) {
//        test(new UnionFind_UF(12));
//        testTime(new UnionFind_QF(count));
//        testTime(new UnionFind_UF(count));
        testTime(new UnionFind_QU_S(count));
        testTime(new UnionFind_QU_R(count));
        testTime(new UnionFind_QU_R_PC(count));
        testTime(new UnionFind_QU_R_PS(count));
        testTime(new UnionFind_QU_R_PH(count));
        testTime(new GenericUnionFind<Integer>());
    }

    static void testTime(GenericUnionFind<Integer> uf) {
        for (int i = 0; i < count; i++) {
            // 生成集合
            uf.makeSet(i);
        }

        Times.test(uf.getClass().getSimpleName(), () -> {
            for (int i = 0; i < count; i++) {
                uf.union((int) (Math.random() * count),
                        (int) (Math.random() * count));
            }

            for (int i = 0; i < count; i++) {
                uf.isSame((int) (Math.random() * count),
                        (int) (Math.random() * count));
            }
        });
    }

    static void testTime(UnionFind uf) {
        Times.test(uf.getClass().getSimpleName(), () -> {
            for (int i = 0; i < count; i++) {
                uf.union((int) (Math.random() * count),
                        (int) (Math.random() * count));
            }

            for (int i = 0; i < count; i++) {
                uf.isSame((int) (Math.random() * count),
                        (int) (Math.random() * count));
            }
        });
    }

    private static void test(UnionFind uf) {
        // 集合1
        uf.union(0, 1);
        uf.union(0, 3);
        uf.union(0, 4);
        uf.union(2, 3);
        uf.union(2, 5);

        // 集合2
        uf.union(6, 7);

        // 集合3
        uf.union(8, 10);
        uf.union(9, 10);
        uf.union(9, 11);

        System.out.println(uf.isSame(0, 6));// false
        System.out.println(uf.isSame(0, 5));// true
        System.out.println(uf.isSame(6, 9));// false

        // 合并两个村庄
        uf.union(4, 6);
        System.out.println(uf.isSame(0, 6));// true 村庄连接起来了
    }
}
